#include "GraphExploration.hpp"
#include "GraphFunctions.hpp"
#include <utility>
#include <boost/tuple/tuple.hpp>
#include "ullman.hpp"
#include <boost/graph/isomorphism.hpp>
using namespace std;
using namespace boost;
using namespace TopologicalLearner;

//----------------------------------------------------------------
GraphExploration::GraphExploration(const Graph& G, bool bUnique)
{
    m_G = &G;
    m_PG = Graph();
    m_bUnique = bUnique;
    FillNotAdded();
}
//----------------------------------------------------------------
GraphExploration::GraphExploration(const Graph& G, const Graph& gPartial, bool bUnique)
{
    // Fill everything but those which are in gPartial
    m_G = &G;
    m_PG = gPartial;
    m_bUnique = bUnique;
    FillNotAdded(&m_PG);
}
//----------------------------------------------------------------
void GraphExploration::FillNotAdded(const Graph* pPartial)
{


    m_kNotAdded.clear();
    m_kNotAddedEdges.clear();
    m_PGMap.clear();



    if (!m_bUnique){



      // First run ullman on it


      std::vector<std::pair<size_t,size_t> > mapping;
      VertexLabelPredicate alabel(m_PG,*m_G);
      trueEdgePredicate blabel;
      // If it's not isomorphic, return

      if( pPartial != 0 && !ullmann(m_PG, *m_G, alabel, blabel, mapping) )
      {
          return;
      }

      /* Procedure:
       * 1. Loop through m_G's vertices and add those that are not in mapping to m_kNotAdded
       * 2. Loop through m_PG's edges and get the list of corresponding m_G edges. Then go through m_G's edges
       * and only add those who are not in the former list.
       */


          Iter_t Ibegin, Iend;
          for( tie(Ibegin, Iend) = vertices(*m_G); Ibegin != Iend; ++Ibegin )
          {

              bool isFoundInPG=false;
              if( pPartial != 0 )
              {
                  for (unsigned int i=0; i< mapping.size(); i++){
                      if(mapping[i].second == *Ibegin)
                      { // This comparison holds?
                          //m_PGMap = (vertex of m_G) -> (vertex of partial graph m_PG)
                          m_PGMap[*Ibegin] = mapping[i].first;
                          isFoundInPG=true;
                          break;
                      }
                  }
              }
              else
                isFoundInPG = false; // Add everything to the not added if pPartial == 0
              if(!isFoundInPG){
                  m_kNotAdded.push_back(*Ibegin);
              }
          }


          random_shuffle( m_kNotAdded.begin(), m_kNotAdded.end() );

          //edges(*pPartial);


          // First get the m_G descriptors of common edges
          vector<Edge> commonEdges;
          graph_traits<Graph>::edge_iterator firstE, lastE;
          if( pPartial != 0 )
          {
              for (tie(firstE, lastE) = edges(*pPartial); firstE != lastE; ++firstE)
              {
                  // Get m_PG vertice pair for this edge



                  Vertex uPG = source(*firstE, *pPartial);
                  Vertex vPG = target(*firstE, *pPartial);
                  Vertex uG,vG;


                  // Find corresponding m_G vertices
                  int j=-1;
                  for (unsigned int i=0; i< mapping.size(); i++){
                      if(mapping[i].first == uPG){ // This comparison holds?
                        uG=mapping[i].second;
                         j++ ;
                      }
                      else if (mapping[i].first == vPG){
                          vG=mapping[i].second;
                          j++;
                      }
                  }
                  if(j < 0){
                      cout<< __FILE__ << ":" << __LINE__ << "Could not find mappings between partial graph and the full graph. Returning without doing anything. You should debug this." <<  j << endl;
                      return;
                  }
                  // Finally get the edge in m_G that is also in m_PG
                  commonEdges.push_back((edge(uG, vG, *m_G).first));



              }
          }


          // Now go through m_G's edges and add those who are not in commonEdges
          for (tie(firstE, lastE) = edges(*m_G); firstE != lastE; ++firstE)
          {
              bool isFoundInPG=false;
              if( pPartial != 0 )
              {
                  for (unsigned int i=0; i< commonEdges.size(); i++){
                      if(commonEdges[i] == *firstE){ // This comparison holds?
                          isFoundInPG=true;
                          break;
                      }
                  }
              }
              else
                    isFoundInPG = false;

              if(!isFoundInPG)
                  m_kNotAddedEdges.push_back(*firstE);


          }

          random_shuffle( m_kNotAddedEdges.begin(), m_kNotAddedEdges.end() );

            if( pPartial == 0 )
            {
                // Add one vertex as the partial graph
                Vertex V = m_kNotAdded.back();
                m_kNotAdded.pop_back();

                Vertex VNew = add_vertex(m_PG);
                put(vertex_name, m_PG, VNew, get(vertex_name, *m_G, V));

                m_PGMap[V] = VNew;
            }

            std::map<Vertex, Vertex>::iterator it;
        //    cout << "------ m_PGMap ------" << endl;
            for (it = m_PGMap.begin(); it != m_PGMap.end();++it){
          //      cout << it->first << " , " << it->second << endl;
            }
           // cout << "---------------------------" << endl;
    }
    else{



        // 1. First check if the subgraph is contained in the larger graph
        if( pPartial != 0 && !GraphFunctions::IsSubgraphContained(*pPartial, *m_G) )
            return;

        // Copy all the vertices into a vector and random shuffle them


        Iter_t Ibegin, Iend; tie(Ibegin, Iend) = vertices(*m_G);
        m_kNotAdded.resize(num_vertices(*m_G));

        copy(Ibegin, Iend, m_kNotAdded.begin());

        if( pPartial == 0 )
        {
            // Add one vertex as the partial graph
            Vertex V = m_kNotAdded.back();
            m_kNotAdded.pop_back();

            Vertex VNew = add_vertex(m_PG);
            put(vertex_name, m_PG, VNew, get(vertex_name, *m_G, V));
            //m_PGMap[V] = VNew;
            m_PGMap[V] = VNew;
        }


        // If pPartial != 0, we should remove those vertices which are in pPartial
        // from m_kNotAdded
        // -----------------
        if( pPartial != 0 )
        {
            for( tie(Ibegin, Iend) = vertices(*pPartial); Ibegin != Iend; ++Ibegin )
            {
                int iVID = get(vertex_name, *pPartial, *Ibegin);
                Vertex vRemove = GraphFunctions::FindVertex(iVID, *m_G).second;
                m_PGMap[vRemove] = *Ibegin;
                m_kNotAdded.erase(find(m_kNotAdded.begin(), m_kNotAdded.end(), vRemove));
            }
        }
        // ------------------


        random_shuffle( m_kNotAdded.begin(), m_kNotAdded.end() );
        //---

        // Copy all the edges into a vector and random shuffle them

        graph_traits<Graph>::edge_iterator firstE, lastE;
        tie(firstE, lastE) = edges(*m_G);

        m_kNotAddedEdges.resize(num_edges(*m_G));
        copy(firstE, lastE, m_kNotAddedEdges.begin());

        // If pPartial != 0, we should remove those edges which are in pPartial
        // from m_kNotAddedEdges
        // -----------------
        if( pPartial != 0 )
        {
            graph_traits<Graph>::edge_iterator firstE, lastE;
            for (tie(firstE, lastE) = edges(*pPartial); firstE != lastE; ++firstE)
            {
                //remove_edge(u, v, G);
                int iVuID = get(vertex_name, *pPartial,source(*firstE, *pPartial));
                int iVvID = get(vertex_name, *pPartial,target(*firstE, *pPartial));
                Vertex u = GraphFunctions::FindVertex(iVuID, *m_G).second; //m_PGMap[source(*firstE, *pPartial)];
                Vertex v = GraphFunctions::FindVertex(iVvID, *m_G).second; //m_PGMap[target(*firstE, *pPartial)];
                Edge E = edge(u, v, *m_G).first;
                m_kNotAddedEdges.erase(find(m_kNotAddedEdges.begin(), m_kNotAddedEdges.end(), E));
                //pPartial
            }
        }
        // -----------------

        random_shuffle( m_kNotAddedEdges.begin(), m_kNotAddedEdges.end() );
        //---
    }
}
//----------------------------------------------------------------
GraphExploration::EditOpIterator::EditOpIterator(GraphExploration& GE)
{
    iEOpsLeft = -1;
    iVOpsLeft = -1;
    m_GE = &GE;
    m_G = GE.m_G;
    m_kNotAdded = GE.m_kNotAdded;
    m_kNotAddedEdges = GE.m_kNotAddedEdges;
    //m_LastOp = make_tuple(false, 0, 0);//make_pair(false, false);
    m_LastOp = boost::make_tuple(false, 0, 0);
}
//----------------------------------------------------------------
// Returns a pair where the first component is the ID of the vertex already existing in the partial graph
// while the second component gives the new vertex ID
EditOp GraphExploration::EditOpIterator::NextVertexOp(bool bForceAdd)
{
    // Retreive a vertex not yet added, and which is possible to add at this stage

    if(iVOpsLeft == 0)
        return boost::make_tuple(true, 0, 0);

    for(unsigned int i=0; i < m_kNotAdded.size(); i++)
    {
        // Check if this vertex is addable at this time.
        // This means that there is some edge in the example graph between some already added vertex
        // in the partial graph (so we don't get disconnected parts).

        Vertex VAdd;
        VAdd = m_kNotAdded[i];

        bool bValid = false;

        graph_traits<Graph>::out_edge_iterator firstE, lastE;
        Vertex vAlreadyExistV;
        Edge kToRemove;

        for (tie(firstE, lastE) = out_edges(VAdd, *m_G); firstE != lastE; ++firstE)
        {

            if( source(*firstE,*m_G) == VAdd )
            {


                // So the target must be a vertex already existing
                if( m_GE->m_PGMap.find(target(*firstE,*m_G)) != m_GE->m_PGMap.end() )
                {

                    bValid = true;
                    vAlreadyExistV = m_GE->m_PGMap[target(*firstE,*m_G)];
                    kToRemove = *firstE;
                    break;
                }
            }
        }

        // Force add is used to add the first vertex for instance
        if( bForceAdd || bValid )
        {

            // Add a new vertex to the partial graph and copy all the data from the example graph
            //GraphHandler::Vertex V = add_vertex(m_GE.m_PG);
            //put(vertex_name, m_GE.m_PG, V, get(vertex_name, *m_G, VAdd));

            // Connect it as well using the edge we found
            if( bValid )
            {

                // add_edge(V, vAlreadyExistV, m_GE->m_PG);
                m_kNotAddedEdges.erase(find( m_kNotAddedEdges.begin(), m_kNotAddedEdges.end(), kToRemove));

                //cout << "Adding new vertex " << m_kPartialG[V].sName << " connected from " << m_kPartialG[vAlreadyExistV].sName << endl;
            }

            // Save the correspondence vertex of m_pEGraph -> vertex of partial graph
            // m_GE->m_PGMap[VAdd] = V;

            // Remove it from m_kNotAdded
            m_kNotAdded.erase(m_kNotAdded.begin()+i);

            // Save vAlreadyExistV, vAdd incase we want to perform this edit operation
            m_LastVOp = std::make_pair(vAlreadyExistV, VAdd);



            if( m_GE->m_bUnique )
                m_LastOp = boost::make_tuple(true, get(vertex_name, m_GE->m_PG, vAlreadyExistV), get(vertex_name, *m_G, VAdd));
            else
                m_LastOp = boost::make_tuple(true, vAlreadyExistV, get(vertex_name, *m_G, VAdd));

            //m_LastOp = boost::make_tuple(true, (unsigned int)vAlreadyExistV, (unsigned int) VAdd);

            iVOpsLeft--;

            // If vertex names are not unique, we return <vertex, category> instead of <category,category>.

            return m_LastOp;
        }
    }

    cout << "Failed at graph exploration NextVertexOp" << endl;
    m_LastOp = boost::make_tuple(false,0, 0);
    return boost::make_tuple(false, 0,0);
}
//----------------------------------------------------------------
// Performs the actual edit operation
void GraphExploration::EditOpIterator::operator*()
{

    if(m_LastOp.get<0>())//m_LastOp.first == true && m_LastOp.second == false)
    {
        if( m_GE->m_bUnique )
        {
            // Perform a vertex operation
            Vertex V = add_vertex(m_GE->m_PG);
            put(vertex_name, m_GE->m_PG, V, get(vertex_name, *m_G, m_LastVOp.second));
            // Save the correspondence vertex of m_pEGraph -> vertex of partial graph
            // m_PGMap[VAdd] = V;
            m_GE->m_PGMap[m_LastVOp.second] = V;


            //add_edge(V, vAlreadyExistV, m_GE->m_PG);
            add_edge(V, m_LastVOp.first, m_GE->m_PG);
        }
        else
        {
            Vertex vNew = add_vertex(m_GE->m_PG);
            put(vertex_name, m_GE->m_PG, vNew, m_LastOp.get<2>() );
            m_GE->m_PGMap[m_LastVOp.second] = vNew;

            add_edge(m_LastOp.get<1>(), vNew, m_GE->m_PG);
        }
    }
    else if( !m_LastOp.get<0>() )
    {
        // Perform the edge operation
        //add_edge(m_PGMap[vS], m_PGMap[vT], m_kPartialG);
        if( m_GE->m_bUnique )
            add_edge(m_LastEOp.first, m_LastEOp.second, m_GE->m_PG);
        else
            add_edge( m_LastOp.get<1>(), m_LastOp.get<2>(), m_GE->m_PG );
    }

   // GraphFunctions::PrintEditOp(m_GE->m_PG, m_LastOp);
   // m_GE->m_PG = GraphFunctions::ApplyEditOp(m_GE->m_PG, m_LastOp, m_GE->m_bUnique);

    //m_GE->FillNotAdded(&m_GE->m_PG);
    //m_LastVOp.second

    m_GE->m_kNotAdded = m_kNotAdded;
    m_GE->m_kNotAddedEdges = m_kNotAddedEdges;
    //m_GE->m_PGMap[]


    //EditOpIterator(*m_GE);

    // return *m_GE;
}
//----------------------------------------------------------------
// Returns how many vertex operations there are left to perform
int GraphExploration::EditOpIterator::VertexOperations()
{
    // If the subgraph is not contained in the larger graph then return 0
    if( m_GE->m_PGMap.size() == 0 )
        return 0;

    if( iVOpsLeft == -1 )
    {
        int n = 0;
        for(unsigned int i=0; i < m_kNotAdded.size(); i++)
        {
            bool bValid = false;
            Vertex VAdd = m_kNotAdded[i];

            graph_traits<Graph>::out_edge_iterator firstE, lastE;
            for (tie(firstE, lastE) = out_edges(VAdd, *m_G); firstE != lastE; ++firstE)
                if( source(*firstE,*m_G) == VAdd )
                    // So the target must be a vertex already existing
                    if( m_GE->m_PGMap.find(target(*firstE,*m_G)) != m_GE->m_PGMap.end() )
                    {
                        bValid = true;
                        break;
                    }

            if( bValid )
                n++;
        }
        iVOpsLeft = n;
    }

    return iVOpsLeft;
}
//----------------------------------------------------------------
bool GraphExploration::EditOpIterator::isDoneVertex()
{
    return (VertexOperations() == 0);
}
//----------------------------------------------------------------
EditOp GraphExploration::EditOpIterator::NextEdgeOp()
{

     // TODO: If vertex names are not unique, we return <vertex, vertex> instead of <category,category>.

    if( iEOpsLeft == 0 )
        return boost::make_tuple(false, 0, 0);

    for(unsigned int i=0; i < m_kNotAddedEdges.size(); i++)
    {
        Edge E = m_kNotAddedEdges[i];
        Vertex vS = source(E, *m_G);
        Vertex vT = target(E, *m_G);

        // If both vertices of the edge exist
        if( m_GE->m_PGMap.find(vS) != m_GE->m_PGMap.end() && m_GE->m_PGMap.find(vT) != m_GE->m_PGMap.end() )
        {
            //add_edge(m_PGMap[vS], m_PGMap[vT], m_kPartialG);
            // Save these incase we want to instantiate this edit op
            m_LastEOp = std::make_pair(m_GE->m_PGMap[vS], m_GE->m_PGMap[vT]);

            if( m_GE->m_bUnique )
                m_LastOp =  boost::make_tuple(false, get(vertex_name, *m_G, vS), get(vertex_name, *m_G, vT));
            else
                m_LastOp = boost::make_tuple(false,  m_GE->m_PGMap[vS], m_GE->m_PGMap[vT]);


            //m_LastOp = boost::make_tuple(false, m_GE->m_PGMap[vS], m_GE->m_PGMap[vT]);//make_pair(false, true);

            m_kNotAddedEdges.erase(m_kNotAddedEdges.begin()+i);
            iEOpsLeft--;
            return m_LastOp;
        }
    }

    return boost::make_tuple(false, 0, 0);
}
//----------------------------------------------------------------
int GraphExploration::EditOpIterator::EdgeOperations()
{

    // cout << __LINE__ << endl;
    if( m_GE->m_PGMap.size() == 0 )
        return 0;
    if( iEOpsLeft == -1 )
    {
        // cout << __LINE__ << endl;
        iEOpsLeft = 0;
        for(unsigned int i=0; i < m_kNotAddedEdges.size(); i++)
        {

            Edge E = m_kNotAddedEdges[i];
            Vertex vS = source(E, *m_G);
            Vertex vT = target(E, *m_G);

          //  cout << vS << "," << vT << endl;

            // If both vertices of the edge exist, it is a possible edge addition
            if( m_GE->m_PGMap.find(vS) != m_GE->m_PGMap.end() && m_GE->m_PGMap.find(vT) != m_GE->m_PGMap.end() )
                iEOpsLeft++;
        }
    }

    return iEOpsLeft;
}
//----------------------------------------------------------------
bool GraphExploration::EditOpIterator::isDoneEdge()
{
    return (EdgeOperations() == 0);
}
//----------------------------------------------------------------
